// Created by WXX on 2021/9/27 9:28
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：280 ms, 在所有 C++ 提交中击败了5.19%的用户
 * 内存消耗：21.2 MB, 在所有 C++ 提交中击败了29.87%的用户
 */
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size(), MOD = 1e9 + 7;
        vector<long long> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 26; j++) {
                char a = s[i - 1];  // 最后一位
                if (j <= 9) {
                    if (a == '*' || a == j + '0') f[i] += f[i - 1];
                } else if (i >= 2) {
                    char b = s[i - 2];  // 倒数第二位
                    int y = j / 10, x = j % 10;
                    // * 不能代表0，因此必须要求y和x非零
                    if ((b == y + '0' || b == '*' && y) && (a == x + '0' || a == '*' && x))
                        f[i] += f[i - 2];
                }
                f[i] %= MOD;
            }
        return f[n];
    }
};

int main() {

    cout << Solution().numDecodings("*") << endl;  // 9
    cout << Solution().numDecodings("06") << endl;  // 0
    cout << Solution().numDecodings("1*") << endl;  // 18
    cout << Solution().numDecodings("3*") << endl;  // 9
    cout << Solution().numDecodings("**") << endl;  // 96

    return 0;
}
